package _01_排序;

/*
    计数排序,利用空间换时间
    时间复杂度:O(n+k),空间复杂度:O(n+k)
 */
public class CountingSort08 extends Sort<Integer> {
    //计数排序
    @Override
    protected void sort() {
        //找到数组的最小值和最大值，进行范围控制
        int max = array[0];
        int min = array[0];
        for(int i=1;i<array.length;++i){
            if(max<array[i]){
                max = array[i];
            }
            if(min>array[i]){
                min = array[i];
            }
        }


        //创建counts数组，统计出现次数和排完序的位置信息
        int[] counts = new int[max - min + 1];
        //算出array数组中的元素在counts中出现的次数
        for(int i=0;i<array.length;++i){
            //array[i]在counts中的索引为counts[array[i] - min]
            counts[array[i] - min]++;
        }

        //计算每个元素之前共有多少个元素，除去1,为了等会算出有序序列中的索引
        for(int i=1;i<counts.length;++i){
            counts[i] += counts[i-1];
        }

        //排序,从后往前遍历，排序算法的稳定性
        int[] newArray = new int[array.length]; //有序序列
        for(int i=newArray.length-1;i>=0;--i){
            //array[i]在有序序列中的索引就是 counts[array[i]-min]--
            newArray[--counts[array[i]-min]] = array[i];
        }

        for(int i=0;i<array.length;++i){
            array[i] = newArray[i];
        }
    }

}
